{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #解密数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: crackNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #解密数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有一串神秘的密文 <code>ciphertext</code>，经调查，密文的特点和规则如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>密文由非负整数组成</li>\n",
    "\t<li>数字 0-25 分别对应字母 a-z</li>\n",
    "</ul>\n",
    "\n",
    "<p>请根据上述规则将密文 <code>ciphertext</code> 解密为字母，并返回共有多少种解密结果。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> ciphertext = 216612\n",
    "<strong>输出:</strong> <code>6\n",
    "</code><strong>解释:</strong> 216612 解密后有 6 种不同的形式，分别是 \"cbggbc\"，\"vggbc\"，\"vggm\"，\"cbggm\"，\"cqggbc\" 和 \"cqggm\" </pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= ciphertext &lt; 2<sup>31</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof](https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof](https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        last = ciphertext%10\n",
    "        tmp = ciphertext//10\n",
    "        ppRes,pRes = 1,1\n",
    "        while tmp is not 0:\n",
    "            curr = tmp%10\n",
    "            if curr is 1 or (curr is 2 and last <= 5):\n",
    "                ppRes,pRes=pRes,ppRes+pRes\n",
    "            else:\n",
    "                ppRes=pRes\n",
    "            tmp,last = tmp//10,curr\n",
    "        return pRes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        s = str(ciphertext)\n",
    "        dp = [0]*(len(s)+1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "\n",
    "        for i in range(2,len(s)+1):\n",
    "            if 10 <= 10*int(s[i-2])+int(s[i-1]) <= 25:\n",
    "                dp[i] = dp[i-1] + dp[i-2]\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        p, q, r = 1, 1, 1\n",
    "        flag = ciphertext % 10\n",
    "        ciphertext //= 10\n",
    "        while ciphertext != 0:\n",
    "            num = ciphertext % 10 * 10 + flag\n",
    "            if num < 26 and num > 9:\n",
    "                r = p + q\n",
    "            else:\n",
    "                r = q\n",
    "            flag = ciphertext % 10\n",
    "            ciphertext //= 10\n",
    "            p = q\n",
    "            q = r\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        num = ciphertext\n",
    "        s = str(num)\n",
    "        n = len(s)\n",
    "        if n < 1:\n",
    "            return 0\n",
    "        \n",
    "        # 定义：dp[i] 表示 s[0..i-1] 的解码方式数量\n",
    "        dp = [0 for i in range(n + 1)]\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "\n",
    "        for i in range(2, n + 1):\n",
    "            c = s[i - 1]\n",
    "            d = s[i - 2]\n",
    "            if '0' <= c and c <= '9':\n",
    "                dp[i] += dp[i - 1]\n",
    "            if d == '1' or d == '2' and c <= '5':\n",
    "                dp[i] += dp[i - 2]\n",
    "        \n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        nums = str(ciphertext)\n",
    "        a = b = 1\n",
    "        for i in range(2, len(nums) + 1):\n",
    "            a, b = (a + b if '10' <= nums[i-2 : i] <= '25' else a), a\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        num_str = str(ciphertext)\n",
    "        n = len(num_str)\n",
    "        self.count = 0\n",
    "\n",
    "        def cal_count(x):\n",
    "            if x == n-1 or x == n:\n",
    "                self.count += 1\n",
    "                return\n",
    "\n",
    "            cal_count(x+1)\n",
    "\n",
    "            if '10' <= num_str[x:x+2] <= '25':\n",
    "                cal_count(x+2)\n",
    "            return\n",
    "        \n",
    "        cal_count(0)\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        a = b = 1\n",
    "        y = ciphertext % 10\n",
    "        while ciphertext > 9:\n",
    "            ciphertext //= 10\n",
    "            x = ciphertext % 10\n",
    "            tmp = 10 * x + y\n",
    "            c = a + b if 10 <= tmp <= 25 else a\n",
    "            a, b = c, a\n",
    "            y = x\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        p, q, r = 1, 1, 1\n",
    "        flag = ciphertext % 10\n",
    "        ciphertext //= 10\n",
    "        while ciphertext != 0:\n",
    "            num = ciphertext % 10 * 10 + flag\n",
    "            if num < 26 and num > 9:\n",
    "                r = p + q\n",
    "            else:\n",
    "                r = q\n",
    "            flag = ciphertext % 10\n",
    "            ciphertext //= 10\n",
    "            p = q\n",
    "            q = r\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        a = b = 1\n",
    "        y = ciphertext % 10\n",
    "        while ciphertext > 9:\n",
    "            ciphertext //= 10\n",
    "            x = ciphertext % 10\n",
    "            tmp = 10 * x + y\n",
    "            c = a + b if 10 <= tmp <= 25 else a\n",
    "            a, b = c, a\n",
    "            y = x\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        ciphertext = str(ciphertext)\n",
    "        dp = [0] * (len(ciphertext)+1)\n",
    "        dp[0] = 1\n",
    "        m = {str(k):True for k in range(26)}\n",
    "        for i in range(1, len(ciphertext)+1):\n",
    "            temp = 0\n",
    "            if m.get(ciphertext[i-1:i]) is not None:\n",
    "                temp += dp[i-1]\n",
    "            \n",
    "            if i - 1 >= 0 and m.get(ciphertext[i-2:i]) is not None:\n",
    "                temp += dp[i-2]\n",
    "            dp[i] = temp\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        s = str(ciphertext)\n",
    "        dp=[1 for _ in range(len(s)+1)]\n",
    "        for i in range(2,len(s)+1):\n",
    "            if \"10\"<= s[i-2:i]<=\"25\":\n",
    "                dp[i]=dp[i-1]+dp[i-2]\n",
    "            else:\n",
    "                dp[i]=dp[i-1]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        s = str(ciphertext)\n",
    "        a=b=1\n",
    "        for i in range(2,len(s)+1):\n",
    "            temp = s[i-2:i]\n",
    "            c =  a + b if \"10\"<=temp<=\"25\" else a\n",
    "            b = a\n",
    "            a = c\n",
    "        return a\n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        ciphertext = str(ciphertext)\n",
    "        n = len(ciphertext)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        dp[0] = 1\n",
    "        for i in range(1,n):\n",
    "            if ciphertext[i-1] == '1' or (ciphertext[i-1] == '2' and ciphertext[i] <= '5'):\n",
    "                if i == 1:\n",
    "                    dp[i] = 2\n",
    "                else:\n",
    "                    dp[i] = dp[i-1] + dp[i-2]\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        cip=str(ciphertext)\n",
    "        dp=[0]*len(cip)\n",
    "        dp[0]=1\n",
    "        if len(cip)>1:\n",
    "            if 10<=int(cip[0:2])<26:\n",
    "                dp[1]=2\n",
    "            else:\n",
    "                dp[1]=1\n",
    "            for i in range(2,len(cip)):\n",
    "                if 10<=int(cip[i-1:i+1])<26:\n",
    "                    dp[i]=dp[i-1]+dp[i-2]\n",
    "                else: dp[i]=dp[i-1]\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        s=str(ciphertext)\n",
    "        if len(s)==0:\n",
    "            return 0\n",
    "        res=[0]*(len(s)+1)\n",
    "        res[0]=1\n",
    "        res[1]=1\n",
    "        for i in range(2,len(s)+1):\n",
    "            if s[i-2]!='0' and  0<=int(s[i-2]+s[i-1])<=25:\n",
    "                res[i]=res[i-1]+res[i-2]\n",
    "            else:\n",
    "                res[i]=res[i-1]\n",
    "        # print(res)\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        ciphertext = str(ciphertext)\n",
    "        n = len(ciphertext)\n",
    "        if n <= 1:\n",
    "            return 1\n",
    "        dp = [0] * (n)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 2 if int(ciphertext[0:2]) >= 10 and int(ciphertext[0:2]) <= 25 else 1\n",
    "        for i in range(2, n):\n",
    "            if int(ciphertext[i-1:i+1]) >= 10 and int(ciphertext[i-1:i+1]) <= 25:\n",
    "                dp[i] = dp[i-1] + dp[i-2]\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        s = str(ciphertext)\n",
    "        a = b = 1  \n",
    "        for i in range(1,len(s)):\n",
    "            if '10' <= s[i-1:i+1] <= '25':\n",
    "                a,b = b,a+b\n",
    "            else:\n",
    "                a = b\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        ciphertext = str(ciphertext)\n",
    "        p, q, r = 0, 1, 1\n",
    "        for i in range(1,len(ciphertext)):\n",
    "            p = q\n",
    "            q = r\n",
    "            r = 0\n",
    "            r += q\n",
    "            if int(ciphertext[i-1:i+1]) >= 10 and int(ciphertext[i-1:i+1]) <= 25:\n",
    "                r += p\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        cipher_str = str(ciphertext)\n",
    "        n = len(cipher_str)\n",
    "        dp = [0]*n\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                dp[i] = 1\n",
    "            else:\n",
    "                if cipher_str[i-1] == '0' or int(cipher_str[i-1]+cipher_str[i]) >= 26:\n",
    "                    dp[i] = dp[i-1]\n",
    "                else:\n",
    "                    if i >= 2:\n",
    "                        dp[i] = dp[i-1] + dp[i-2]\n",
    "                    else:\n",
    "                        dp[i] = dp[i-1] + 1\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        tmp=str(ciphertext)\n",
    "        dp=[0]*len(tmp)\n",
    "        dp[0]=1\n",
    "        for i in range(1,len(tmp)):\n",
    "            if tmp[i-1]!='0' and int(tmp[i-1]+tmp[i])<26:\n",
    "                if i==1:\n",
    "                    dp[i]=2\n",
    "                else:\n",
    "                    dp[i]=dp[i-1]+dp[i-2]\n",
    "            else:\n",
    "                dp[i]=dp[i-1]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        n = len(str(ciphertext))\n",
    "        dp = [0]*(n+1)\n",
    "        dp[1] = 1\n",
    "        dp[0] = 1\n",
    "        if n < 2:\n",
    "            return dp[n]\n",
    "        else:\n",
    "            for i in range(2,n+1):\n",
    "                temp = str(ciphertext)[i-2:i]\n",
    "                if \"10\" <= temp <= \"25\" :\n",
    "                    dp[i] = dp[i-1]+dp[i-2]\n",
    "                else:\n",
    "                    dp[i] = dp[i-1]\n",
    "            return dp[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        ciphertext = str(ciphertext)\n",
    "        n =len(ciphertext)\n",
    "        dp = [None]*(n+1)\n",
    "        dp[0],dp[1] = 1,1\n",
    "        for i in range(2,n+1):\n",
    "            x,y = int(ciphertext[i-2]),int(ciphertext[i-1])\n",
    "            s = 10*x+y\n",
    "            if (s>=10) and (s<26):\n",
    "                dp[i] = dp[i-1]+dp[i-2]\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:        \n",
    "        s = str(ciphertext)\n",
    "        n = len(s)\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for i in range(2, n + 1):\n",
    "            if '10' <= s[i - 2:i] <= \"25\":\n",
    "                dp[i] = dp[i - 1] + dp[i - 2]\n",
    "            else:\n",
    "                dp[i] = dp[i - 1]\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        #动态规划：注意数字 0-25 \n",
    "        s = str(ciphertext)\n",
    "        a = b = 1\n",
    "        for i in range(2, len(s) + 1):\n",
    "            tmp = s[i - 2:i]\n",
    "            c = a + b if \"10\" <= tmp <= \"25\" else a\n",
    "            b = a\n",
    "            a = c\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, num: int) -> int:\n",
    "        prepre=0\n",
    "        pre=1\n",
    "        result=0\n",
    "        numstr=str(num)\n",
    "        for i in range(len(numstr)):\n",
    "            result=0\n",
    "            result+=pre \n",
    "            if i>0 and 10<=int(numstr[i-1:i+1])<=25:\n",
    "                result+=prepre \n",
    "            prepre=pre \n",
    "            pre=result \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        # 最后两位如果<=25，可以翻译成1个字母，也可以翻译成2个字母\n",
    "        # 最后两位如果>25,只能翻译成两个字母\n",
    "        if ciphertext < 10:\n",
    "            return 1\n",
    "        elif ciphertext >= 10 and ciphertext <= 25:\n",
    "            return 2\n",
    "        elif ciphertext > 25 and ciphertext < 100:\n",
    "            return 1\n",
    "        else:\n",
    "            last_two_num = ciphertext - (ciphertext // 100) * 100\n",
    "            if last_two_num >= 10 and last_two_num <= 25:\n",
    "                return self.crackNumber(ciphertext // 100) + self.crackNumber(ciphertext // 10)\n",
    "            elif last_two_num < 10 or last_two_num > 25:\n",
    "                return self.crackNumber(ciphertext // 10)\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        s = str(ciphertext)\n",
    "        a = b = 1\n",
    "        for i in range(2,len(s)+1):\n",
    "            tmp = s[i-2:i]\n",
    "            c = a+b if '10'<=tmp<='25' else a\n",
    "            b = a\n",
    "            a = c\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        ans = 0\n",
    "        ciphertext_str = str(ciphertext)\n",
    "        n = len(ciphertext_str)\n",
    "        dp = [1] * (n + 1)\n",
    "        for i in range(2, n + 1):\n",
    "            dp[i] = dp[i - 1]\n",
    "            current_n = int(ciphertext_str[i - 2: i])\n",
    "            if 9 < current_n < 26:\n",
    "                dp[i] = dp[i - 2] + dp[i - 1]\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        nums = str(ciphertext)\n",
    "        a = b = 1\n",
    "        for i in range(2, len(nums) + 1):\n",
    "            a, b = (a + b if '10' <= nums[i-2:i] <= '25' else a), a\n",
    "        return a \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backtrack(self, ciphertext, start, path):\n",
    "        if start == len(ciphertext):\n",
    "            self.res.append(''.join(path))\n",
    "            return\n",
    "        path.append(chr(ord(ciphertext[start]) - ord('0') + ord('a')))\n",
    "        self.backtrack(ciphertext, start + 1, path)\n",
    "        path.pop()        \n",
    "        if ciphertext[start] != '0' and start < len(ciphertext) - 1:\n",
    "            num = (ord(ciphertext[start]) - ord('0')) * 10 + (ord(ciphertext[start + 1]) - ord('0'))\n",
    "            if num <= 25:\n",
    "                path.append(chr(num + ord('a')))\n",
    "                self.backtrack(ciphertext, start + 2, path)\n",
    "                path.pop()\n",
    "            \n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        self.res = []\n",
    "        self.backtrack(str(ciphertext), 0, [])\n",
    "        return len(self.res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        s = str(ciphertext)\n",
    "        a = b = 1\n",
    "        for i in range(2, len(s) + 1):\n",
    "            c = a + b if \"10\" <= s[i-2:i] <= \"25\" else b\n",
    "            a, b = b, c\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        a,b = 1,1\n",
    "        text = str(ciphertext)\n",
    "        for i in range(2,len(text)+1):\n",
    "            tmp = text[i-2:i]\n",
    "            c = a+b if (10 <= int(tmp) <= 25) else b\n",
    "            a = b\n",
    "            b = c\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        s = str(ciphertext)\n",
    "        dp = [0] *(len(s)+1)\n",
    "        dp[0]=dp[1]=1\n",
    "        for i in range (2,(len(s)+1)):\n",
    "            tmp = s[i-2:i]\n",
    "            if \"10\" <= tmp <= \"25\":\n",
    "                dp[i] = dp[i-1]+dp[i-2]\n",
    "            else:\n",
    "                dp[i]=dp[i-1]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        s = str(ciphertext)\n",
    "        if not s:\n",
    "            return 0\n",
    "        a, b = 1, 1\n",
    "        for i in range(2, len(s) + 1):\n",
    "            tmp = s[i-2: i]\n",
    "            c = a + b if \"10\" <= tmp <= \"25\" else b\n",
    "            a = b\n",
    "            b = c % 1000000007\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        astr = str(ciphertext)\n",
    "        n = len(astr)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        res = [0]*n\n",
    "        res[0]=1\n",
    "        if astr[0]=='1' or (astr[0]=='2' and int(astr[1])<=5):\n",
    "            res[1]=2\n",
    "        else:\n",
    "            res[1]=1\n",
    "        for i in range(2, n):\n",
    "            if astr[i-1]=='1' or (astr[i-1]=='2' and int(astr[i])<=5):\n",
    "                res[i]=res[i-1]+res[i-2]\n",
    "            else:\n",
    "                res[i]=res[i-1]\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        a = b = 1\n",
    "        y = ciphertext % 10\n",
    "        while ciphertext != 0:\n",
    "            ciphertext //= 10\n",
    "            x = ciphertext % 10\n",
    "            a, b = (a+b if 10 <= 10*x+y <= 25 else a), a\n",
    "            y = x\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        s = str(ciphertext)\n",
    "        dp = [0] *(len(s)+1)\n",
    "        dp[0]=dp[1]=1\n",
    "        for i in range (2,(len(s)+1)):\n",
    "            tmp = s[i-2:i]\n",
    "            if \"10\" <= tmp <= \"25\":\n",
    "                dp[i] = dp[i-1]+dp[i-2]\n",
    "            else:\n",
    "                dp[i]=dp[i-1]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        s = str(ciphertext)\n",
    "        a = b = 1\n",
    "        for i in range(2, len(s)+1):\n",
    "            tmp = s[i-2:i]\n",
    "            c = a+b if '10' <= tmp <='25' else a\n",
    "            b = a\n",
    "            a = c\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        dp = [0 for _ in range(len(str(ciphertext)))]\n",
    "        dp[0] = 1\n",
    "        for idx in range(1, len(dp)):\n",
    "            dp[idx] += dp[idx - 1]\n",
    "            if 9<int(str(ciphertext)[idx - 1:idx + 1]) < 26:\n",
    "                if idx - 2 >= 0:\n",
    "                    dp[idx] += dp[idx - 2]\n",
    "                else:\n",
    "                    dp[idx] += 1\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        ciphertext = str(ciphertext)\n",
    "        dp = [1] + [0] * len(ciphertext)\n",
    "        for i in range(len(ciphertext)):\n",
    "            if i == 0:\n",
    "                dp[i + 1] = 1\n",
    "            else:\n",
    "                if ciphertext[i-1] != '0' and 10 <= int(ciphertext[i-1]+ciphertext[i]) <= 25:\n",
    "                    dp[i+1] = dp[i] + dp[i-1]\n",
    "                else:\n",
    "                    dp[i+1] = dp[i]\n",
    "        return dp[-1] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        ciphertext = str(ciphertext)\n",
    "        self.res = 0\n",
    "\n",
    "        def dfs(x):\n",
    "            if x >= len(ciphertext) - 1:\n",
    "                self.res += 1\n",
    "                return\n",
    "            dfs(x+1)\n",
    "            if '10' <= ciphertext[x:x+2] <= '25':\n",
    "                dfs(x+2)\n",
    "        \n",
    "        dfs(0)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        char = list(str(ciphertext))\n",
    "        dp = [0] * (len(char) + 1)\n",
    "        dp[0] = 1\n",
    "        dp[1] = 1\n",
    "        for i in range(2, len(char)+1):\n",
    "            if  10 <= int(''.join(char[i-2:i])) <= 25:\n",
    "                dp[i] = dp[i-1] + dp[i-2]\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        ans = 0\n",
    "        ciphertext_str = str(ciphertext)\n",
    "        n = len(ciphertext_str)\n",
    "        dp = [1] * n\n",
    "        for i in range(1, n):\n",
    "            dp[i] = dp[i - 1]\n",
    "            current_n = int(ciphertext_str[i - 1: i + 1])\n",
    "            print(current_n)\n",
    "            if 9 < current_n < 26:\n",
    "                dp[i] = dp[i - 2] + dp[i - 1]\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        str1 = str(ciphertext)\n",
    "        n = len(str1)\n",
    "        dp = [0] * (n+1)\n",
    "        dp[0]=dp[1]=1\n",
    "        for i in range(1, n+1):\n",
    "            tmp = str1[i-2:i]\n",
    "            if '10' <= tmp <= '25':\n",
    "                dp[i] = dp[i-1] + dp[i-2]\n",
    "            else:\n",
    "                dp[i] = dp[i-1]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        nums = str(ciphertext)\n",
    "        a = b = 1\n",
    "        for i in range(2, len(nums) + 1):\n",
    "            a, b = (a + b if '10' <= nums[i - 2: i] <= '25' else a ), a\n",
    "        return a \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        s = str(ciphertext)\n",
    "        n = len(s)\n",
    "        s = ' ' + s\n",
    "        f = [0] * 3\n",
    "        f[0] = 1\n",
    "        for i in range(1,n + 1):\n",
    "            f[i % 3] = 0\n",
    "            a = ord(s[i]) - ord('0')\n",
    "            b = ( ord(s[i - 1]) - ord('0') ) * 10 + a\n",
    "            if 0 <= a <= 9:\n",
    "                f[i % 3] = f[(i - 1) % 3]\n",
    "            if 10 <= b <= 25:\n",
    "                f[i % 3] += f[(i - 2) % 3]\n",
    "        return f[n % 3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        text = str(ciphertext)\n",
    "        # dp[i] = dp[i-1] + dp[i-2], 相邻的两位数  在 [10, 25] 区间\n",
    "        # dp[i] = dp[i-1],           相邻的两位数不在 [10, 25] 区间\n",
    "        a = b = 1    # a: dp[i-1], b: dp[i-2]\n",
    "        a=b=1\n",
    "        for i in range(2,len(text)+1):\n",
    "            if '10'<= text[i-2: i] <= '25':\n",
    "                a,b = a+b, a\n",
    "            else:\n",
    "                a,b = a,a\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        if ciphertext < 10 :\n",
    "            return 1\n",
    "        if ciphertext <= 25 :\n",
    "            return 2\n",
    "        return self.crackNumber(ciphertext//10) + self.crackNumber(ciphertext//100) if 10 <= ciphertext%100 <= 25 else self.crackNumber(ciphertext//10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        # dp求解\n",
    "        # tmp = str(ciphertext)\n",
    "        # len_1 = len(tmp)\n",
    "        # dp = [0] * (len_1 + 1)\n",
    "        # dp[0], dp[1] = 1, 1\n",
    "        # for i in range(2, len_1 + 1):\n",
    "        #     if 10 <= int(tmp[i-2]) * 10 + int(tmp[i-1]) <=25:\n",
    "        #         dp[i] = dp[i-1] + dp[i-2]\n",
    "        #     else:\n",
    "        #         dp[i] = dp[i-1]\n",
    "        # return dp[len_1]\n",
    "\n",
    "        # 空间复杂度为常数的解决方法\n",
    "        a, b = 1, 1\n",
    "        tmp = ciphertext\n",
    "        r = tmp % 10\n",
    "        while tmp:\n",
    "            tmp = tmp // 10 # 去掉最后一个数字\n",
    "            l = tmp % 10\n",
    "            c = a + b if 10 <= l * 10 + r <= 25 else b\n",
    "            a, b = b, c\n",
    "            r = l # 新的余数\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        if ciphertext == 0:\n",
    "            return 1\n",
    "        digits = []\n",
    "        temp = ciphertext\n",
    "        while temp != 0:\n",
    "            digits.append(temp % 10)\n",
    "            temp //= 10\n",
    "        digits.reverse()\n",
    "        n = len(digits)\n",
    "        f = [0] * n\n",
    "        f[0] = 1\n",
    "        for i in range(1, n):\n",
    "            f[i] = f[i - 1]\n",
    "            if digits[i - 1] != 0:\n",
    "                temp_num = digits[i - 1] * 10 + digits[i]\n",
    "                if temp_num >= 10 and temp_num <= 25:\n",
    "                    f[i] += f[i - 2] if i - 2 >= 0 else 1\n",
    "        return f[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        text = str(ciphertext)\n",
    "        a = b = 1\n",
    "        for i in range(2, len(text)+1):\n",
    "            c = a+b if '10' <= text[i-2:i] <= '25' else b\n",
    "            a = b\n",
    "            b = c\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def crackNumber(self, ciphertext: int) -> int:\n",
    "        s = str(ciphertext)\n",
    "        a, b = 1, 1\n",
    "        for i in range(2, len(s)+1):\n",
    "            tmp = s[i-2:i]\n",
    "            c = a + b if \"10\" <= tmp <= \"25\" else a\n",
    "            b = a\n",
    "            a = c\n",
    "        return a"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
